
#include "Vertex.h"
#include "RankSet.h"
#include "Group.h"
#include "VertexDirectory.h"
#include "Chain.h"
#include <cstdlib>
#include "SwitchVerticesAlgorithm.h"
#include "Helpers.h"

//---------------------------------------------------------------------------------
// Public
//---------------------------------------------------------------------------------

//---------------------------------------------------------------------------------
// Ctor
//---------------------------------------------------------------------------------
SwitchVerticesAlgorithm::SwitchVerticesAlgorithm(Chain *inputChain, unsigned int maxInterchangeables): 
m_Chain(inputChain), m_MaxInterchangeables(maxInterchangeables)
{}

//---------------------------------------------------------------------------------
// SwitchSingles: Returns a new chain with one extra group
// The group is created by switching single vertices and running a greedy algorithm
// Note: This method may throw an std::bad_alloc exception due to memory allocation memory
// when initiating a copy of the vertex directory.
//---------------------------------------------------------------------------------
Chain* SwitchVerticesAlgorithm::SwitchSingles()
{
	Logger::LogMessage("Running switch singles");
	// create a VertexDirectory copy and use it in this run (so we don't influance the state of the graph)
	VertexDirectory* dir;
	if (m_Chain->GetDirectory() == NULL)
	{	// use static vertex directory to create the copy
		dir = new VertexDirectory(VertexDirectory::GetStaticCopyVertices());
	}
	else
	{	// use the provided vertex directory to create the copy
		dir = new VertexDirectory(m_Chain->GetDirectory()->GetWorkingCopyVertices());
	}

	Logger::LogMessage("Copying chain");
	Chain *workingCopyChain = m_Chain->CloneFromVertexDirectoryAndUpdateIt(dir);
	Logger::LogMessage("Finding replacements");
	if (workingCopyChain == NULL)	//memory allocation failed
	{
		Logger::LogMessage("copy chain wasn't created in SwitchVerticesAlgorithm::SwitchSingles and the algorithm didn't run.");
		delete dir;
		return NULL;
	}
	
	FindReplacementsForWholeChain(workingCopyChain);

	Logger::LogMessage("Returning interchangeables to graph");
	PutInterchangeablesBackInGraph(workingCopyChain);

	ImproveGroups(workingCopyChain, true);
		
	ReturnRemainingInterchangeablesToGroups(workingCopyChain->GetGraph(),workingCopyChain->GetDirectory());
	
	Logger::LogMessage("Clearing all switching data");
	ClearAllInterchangeableInformation(workingCopyChain->GetDirectory());
	
	Logger::LogMessage("Updating vertex directory from original chain");
	// Return a copy of this chain with the vertices taken from the original directory	
	Chain *returnChain = workingCopyChain->CloneFromVertexDirectoryAndUpdateIt(m_Chain->GetDirectory());
	if (returnChain == NULL)	//memory allocation failed
	{
		delete workingCopyChain;
		delete dir;
		Logger::LogMessage("chain wasn't created in SwitchVerticesAlgorithm::SwitchSingles and the algorithm didn't run.");
		throw new GraphColoringException("chain wasn't created in SwitchVerticesAlgorithm::SwitchSingles and the algorithm didn't run.");
	}

	// Clean up
	delete workingCopyChain;
	delete dir;
	
	return returnChain;
}

//---------------------------------------------------------------------------------
// SwitchCouples
// Note: This method may throw an std::bad_alloc exception due to memory allocation memory
// when initiating a copy of the vertex directory.
//---------------------------------------------------------------------------------
Chain* SwitchVerticesAlgorithm::SwitchCouples()
{
	Logger::LogMessage("Running switch couples");
	// create a VertexDirectory copy and use it in this run (so we don't influance the state of the graph)
	VertexDirectory* dir;
	if (m_Chain->GetDirectory() == NULL)
	{	// use static vertex directory to create the copy
		dir = new VertexDirectory(VertexDirectory::GetStaticCopyVertices());
	}
	else
	{	// use the provided vertex directory to create the copy
		dir = new VertexDirectory(m_Chain->GetDirectory()->GetWorkingCopyVertices());
	}

	Logger::LogMessage("Copying chain");
	Chain *workingCopyChain = m_Chain->CloneFromVertexDirectoryAndUpdateIt(dir);
	if (workingCopyChain == NULL)	//memory allocation failed
	{
		delete dir;
		Logger::LogMessage("copy chain wasn't created in SwitchVerticesAlgorithm::SwitchSingles and the algorithm didn't run.");
		throw new GraphColoringException("copy chain wasn't created in SwitchVerticesAlgorithm::SwitchSingles and the algorithm didn't run.");
	}
	
	Logger::LogMessage("Finding replacements");
	FillVertexSetReplacements(workingCopyChain);

	Logger::LogMessage("Returning interchangeables to graph");
	PutInterchangeableVertexSetsInGraph(workingCopyChain);

	ImproveGroups(workingCopyChain, false);

	ReturnRemainingInterchangeableVertexSetsToGroups(workingCopyChain->GetGraph());

	Logger::LogMessage("Clearing all switching data");
	ClearAllInterchangeableInformation(workingCopyChain->GetDirectory());
	
	Logger::LogMessage("Updating vertex directory from original chain");
	// Return a copy of this chain with the vertices taken from the original directory	
	Chain *returnChain = workingCopyChain->CloneFromVertexDirectoryAndUpdateIt(m_Chain->GetDirectory());
	if (returnChain == NULL)	//memory allocation failed
	{
		delete workingCopyChain;
		delete dir;
		Logger::LogMessage("chain wasn't created in SwitchVerticesAlgorithm::SwitchSingles and the algorithm didn't run.");
		throw new GraphColoringException("chain wasn't created in SwitchVerticesAlgorithm::SwitchSingles and the algorithm didn't run.");
	}

	// Clean up
	delete workingCopyChain;
	delete dir;
	
	return returnChain;
}

//---------------------------------------------------------------------------------
// Private
//---------------------------------------------------------------------------------

//---------------------------------------------------------------------------------
// FindReplacementsForWholeChain: Goes over all groups in chain and marks all 
// available replacement and interchangeable vertices
//---------------------------------------------------------------------------------
void SwitchVerticesAlgorithm::FindReplacementsForWholeChain(Chain *chain)
{
	list<Group*>::iterator it;
	for (it = chain->NonPermutationsGroupsBegin(); it != chain->End(); it++)
	{
		FillReplacements(*it);
	}
	char buffer[15];
	_itoa_s(m_InterchangeableVertices.size(),buffer,15,10);
	string message = "Found ";
	message.append(buffer);
	message.append(" interchangeable vertices");
	Logger::LogMessage(message);
}

//---------------------------------------------------------------------------------
// FillReplacements: Goes over all vertices in group, finds replacements and marks
// them for all vertices in group and saves interchangeable vertices in list 
//---------------------------------------------------------------------------------
void SwitchVerticesAlgorithm::FillReplacements(Group *group)
{
	list<VertexKey> names = group->VerticesNames();
	list<VertexKey>::iterator it;
	for (it = names.begin(); it != names.end() && m_InterchangeableVertices.size() < m_MaxInterchangeables ; it++)
	{
		Vertex *vertex = *(group->Find(*it));
		vertex->FindReplacements();
		if (vertex->Interchangeable())
		{
			m_InterchangeableVertices.insert(*it);
		}

		if (m_InterchangeableVertices.size() == m_MaxInterchangeables)
		{
			Debug::PrintDebugMsg("Maximum interchangeable count reached");
		}
	}
}	

//---------------------------------------------------------------------------------
// FillVertexSetReplacements: Goes over all vertices in group, finds replacements and marks
// them for all vertices in group and saves interchangeable vertices in list 
//---------------------------------------------------------------------------------
void SwitchVerticesAlgorithm::FillVertexSetReplacements(Chain *chain)
{
	list<Group*>::iterator it;
	for (it = chain->NonPermutationsGroupsBegin(); it != chain->End(); it++)
	{
		(*it)->PairUpVerticesAndFindReplacements(chain->GetGraph());
	}

	map<VertexSetKey, VertexSet*> *vertexSets = VertexDirectory::GetSavedVertexSets();
	map<VertexSetKey, VertexSet*>::iterator setIt;
	for (setIt = vertexSets->begin(); setIt != vertexSets->end(); setIt++)
	{
		if (setIt->second->Interchangeable())
		{
			m_InterchangeableVertexSets.insert(setIt->first);
		}
	}

	char buffer[15];
	_itoa_s(m_InterchangeableVertexSets.size(),buffer,15,10);
	string message = "Found ";
	message.append(buffer);
	message.append(" interchangeable vertex sets");
	Logger::LogMessage(message);
}

//---------------------------------------------------------------------------------
// PutInterchangeablesBackInGraph: returns all interchangeable vertices to the graph
//---------------------------------------------------------------------------------
void SwitchVerticesAlgorithm::PutInterchangeablesBackInGraph(Chain *workingChain)
{
	set<VertexKey>::iterator it;
	for (it = m_InterchangeableVertices.begin(); it != m_InterchangeableVertices.end(); it++)
	{
		Vertex *vertex = VertexDirectory::GetVertexFromDirectory(*it, workingChain->GetDirectory());
		
		Group *currentGroup = dynamic_cast<Group*>(vertex->GetPreviousContainer());
		if (currentGroup == NULL)
		{
			throw new GraphColoringException("Previous container is not a group");
		}

		currentGroup->RemoveVertex(vertex);
		(workingChain->GetGraph())->InsertVertex(vertex);	

		string message = vertex->PrintName();
		message.append(" is now in graph");
		Debug::PrintDebugMsg(message);
	}
}

//---------------------------------------------------------------------------------
// PutInterchangeableVertexSetsInGraph: returns all interchangeable vertices to the graph
//---------------------------------------------------------------------------------
void SwitchVerticesAlgorithm::PutInterchangeableVertexSetsInGraph(Chain *workingChain)
{
	set<VertexSetKey>::iterator it;
	for (it = m_InterchangeableVertexSets.begin(); it != m_InterchangeableVertexSets.end(); it++)
	{
		VertexSet *vertex = VertexDirectory::GetVertexSet(*it);
		
		Group *currentGroup = dynamic_cast<Group*>(vertex->GetPreviousContainer());
		if (currentGroup == NULL)
		{
			throw new GraphColoringException("Previous container is not a group");
		}

		currentGroup->RemoveVertexSet(vertex);
		(workingChain->GetGraph())->InsertVertexSet(vertex);	

		string message = vertex->PrintName();
		message.append(" is now in graph");
		Debug::PrintDebugMsg(message);
	}
}

//---------------------------------------------------------------------------------
// ImproveGroups: Runs a version of the greedy algorithm on all groups in chain
//---------------------------------------------------------------------------------
void SwitchVerticesAlgorithm::ImproveGroups(Chain *workingChain, bool switchSingles)
{
	list<Group*>::iterator it;
	for (it = workingChain->NonPermutationsGroupsBegin(); it != workingChain->End(); it++)
	{
		string message =  "Improving group ";
		char buffer[10];
		_itoa_s( (*it)->GetGroupName(), buffer, 10, 10);
		message.append(buffer);
		Logger::LogMessage(message);

		if (switchSingles)
		{
			RunGreedyAlgorithm(workingChain, *it);
		} else
		{
			RunCouplesGreedyAlgorithm(workingChain, *it);
		}
	}
}

//---------------------------------------------------------------------------------
// RunGreedyAlgorithm: 
// Runs a greedy algorithm to improve the given group. This version of the greedy
// algorithm makes additional checks for interchangeable vertices when it checks
// if it is legal to add a vertex to a group, replaces interchangeable vertices
// if needed and updates replacement listings
// Parameters:
// Chain *chain - the chain to work on
// Group *group - the group to improve
// Returns: the improved group
//---------------------------------------------------------------------------------
Group *SwitchVerticesAlgorithm::RunGreedyAlgorithm(Chain *chain, Group *group)
{
	Logger::LogMessage("Running greedy algo while switching");
	VertexDirectory *dir = chain->GetDirectory();
	Graph *tempGraph = chain->GetGraph();

	Debug::PrintDebugMsg("Getting minimal vertex");
	Vertex* vertex = tempGraph->GetMinimalRankedVertex(group, true);
	while (vertex != NULL)
	{  
		// If this vertex is a replacement vertex, remove it from all replacement lists
		if (vertex->IsReplacement())
		{
			string message = "Removing ";
			message.append(vertex->PrintName());
			message.append(" from replacements");
			Debug::PrintDebugMsg(message);

			vertex->ResetIsReplacement();
		} 
		// If this vertex is interchangeable, we have to replace it
		if (vertex->Interchangeable())
		{
			Group *oldGroup = dynamic_cast<Group*>(vertex->GetPreviousContainer());
			if (oldGroup == group)
			{
				Debug::PrintDebugMsg(vertex->PrintName()+" is chosen for its original group!");
				vertex->ResetInterchangeable();
			} else
			{
				string message = "Replacing ";
				message.append(vertex->PrintName());
				Debug::PrintDebugMsg(message);

				vertex->Replace(tempGraph);
			}
			set<VertexKey>::iterator vertexInSet = m_InterchangeableVertices.find(vertex->Name());
			if (vertexInSet == m_InterchangeableVertices.end())
			{
				throw new GraphColoringException("Interchangeable vertex was not in list!");
			}
			// Remove it from interchangeable list, we don't need to take care of it anymore
			m_InterchangeableVertices.erase(vertexInSet);			
		}

		string msg = "Inserting vertex ";
		msg.append(vertex->PrintName());
		msg.append(" to new group, size will be ");
		char size[10];
		_itoa_s(group->Size()+1,size,10);
		msg.append(size);
		Debug::PrintDebugMsg(msg);

		// vertex is a legal vertex to add to the group
		group->InsertNewVertex(vertex);
		Debug::PrintDebugMsg("Updating neighbour status");
		// Update all replacement neighbours that they can not replace in this group anymore
		vertex->UpdateReplacementStateForAllNeighboursInGraph();
		// If there are vertices that have to be replaced, take care of them
		MakeNecessaryReplacements(dir, tempGraph);

		Debug::PrintDebugMsg("Getting minimal vertex");
	    vertex = tempGraph->GetMinimalRankedVertex(group, true);

	}

	return group;	
}

//---------------------------------------------------------------------------------
// RunCouplesGreedyAlgorithm: 
// Runs a couples greedy algorithm to improve the given group. This version of the 
// greedy algorithm makes additional checks for interchangeable vertices when it 
// checks if it is legal to add a vertex to a group, replaces interchangeable 
// vertices if needed and updates replacement listings
// Parameters:
// Chain *chain - the chain to work on
// Group *group - the group to improve
// Returns: the improved group
//---------------------------------------------------------------------------------
Group *SwitchVerticesAlgorithm::RunCouplesGreedyAlgorithm(Chain *chain, Group *group)
{
	Logger::LogMessage("Running couples greedy algo while switching");
	VertexDirectory *dir = chain->GetDirectory();
	Graph *tempGraph = chain->GetGraph();

	Debug::PrintDebugMsg("Getting minimal vertex");
	VertexSet* vertex = tempGraph->GetMinimalRankedVertexCouple(group, true);
	while (vertex != NULL && vertex->Size() == 2)
	{  
		string msg = "Inserting vertex ";
		msg.append(vertex->PrintName());
		msg.append(" to new group, size will be ");
		char size[10];
		_itoa_s(group->Size()+2,size,10);
		msg.append(size);
		Debug::PrintDebugMsg(msg);

		// vertex is a legal vertex to add to the group
		group->InsertNewVertex(vertex);

		// If this vertex is a replacement vertex, remove it from all replacement lists
		if (vertex->IsReplacement())
		{
			vertex->ResetIsReplacement();
		} 
		// If this vertex is interchangeable, we have to replace it
		if (vertex->Interchangeable())
		{
			vertex->Replace(tempGraph);			
		}
		
		Debug::PrintDebugMsg("Updating neighbour status");
		// Update all replacement neighbours that they can not replace in this group anymore
		vertex->UpdateReplacementStateForAllNeighboursInGraph();
		Debug::PrintDebugMsg("Updating containing vertexsets");
		vertex->ClearContainingSets();
		Debug::PrintDebugMsg("Checking for necessary replacements");
		// If there are vertices that have to be replaced, take care of them
		MakeNecessaryReplacementsForVertexSets(tempGraph);

		Debug::PrintDebugMsg("Getting minimal vertex");
		vertex = tempGraph->GetMinimalRankedVertexCouple(group, true);

	}

	return group;	
}

//---------------------------------------------------------------------------------
// ReturnRemainingInterchangeablesToGroups: Goes over the interchangeables the algorithm 
// found and returns them to groups
//---------------------------------------------------------------------------------
void SwitchVerticesAlgorithm::ReturnRemainingInterchangeablesToGroups(Graph *graph, VertexDirectory *dir)
{
	set<VertexKey>::iterator it;
	Logger::LogMessage("Returning remaining interchangeables to groups");
	for (it = m_InterchangeableVertices.begin(); it != m_InterchangeableVertices.end(); it++)
	{
		// Check each interchangeable and see if its in the graph. If it is, return it
		Vertex *currentVertex = VertexDirectory::GetVertexFromDirectory((*it),dir);
		if (currentVertex->IsInGraph())
		{
			string message = "Returning ";
			message.append(currentVertex->PrintName());
			message.append(" to group");
			Debug::PrintDebugMsg(message);

			Group *group = dynamic_cast<Group*>(currentVertex->GetPreviousContainer());
			if (group != NULL)
			{
				if (group->IsLegalToAdd(currentVertex,false))
				{
					graph->RemoveVertex(currentVertex);
					currentVertex->ReturnToOriginalContainer();			
				}
			}
		} else
		{
			string message = currentVertex->PrintName();
			message.append(" is an interchangeable in a group, not returning");
			Debug::PrintDebugMsg(message);
		}
	}
}

//---------------------------------------------------------------------------------
// ReturnRemainingInterchangeablesToGroups: Goes over the interchangeables the algorithm 
// found and returns them to groups
//---------------------------------------------------------------------------------
void SwitchVerticesAlgorithm::ReturnRemainingInterchangeableVertexSetsToGroups(Graph *graph)
{
	set<VertexSetKey>::iterator it;
	Logger::LogMessage("Returning remaining interchangeables to groups");
	for (it = m_InterchangeableVertexSets.begin(); it != m_InterchangeableVertexSets.end(); it++)
	{
		// Check each interchangeable and see if its in the graph. If it is, return it
		VertexSet *currentVertex = VertexDirectory::GetVertexSet(*it);
		if (currentVertex->IsInGraph())
		{
			string message = "Returning ";
			message.append(currentVertex->PrintName());
			message.append(" to group");
			Debug::PrintDebugMsg(message);

			Group *group = dynamic_cast<Group*>(currentVertex->GetPreviousContainer());
			if (group != NULL)
			{
				if (group->IsLegalToAdd(currentVertex,false))
				{
					graph->RemoveVertexSet(currentVertex);
					currentVertex->ReturnToOriginalContainer();			
				}
			}
		} else
		{
			string message = currentVertex->PrintName();
			message.append(" is an interchangeable vertex set in a group, not returning");
			Debug::PrintDebugMsg(message);
		}
	}
}

//------------------------------------------------------------------------------
// MakeNecessaryReplacements: checks the interchangeable list for vertices that
// have to be replaced because they cannot return to their original group
// and replaces them
//---------------------------------------------------------------------------------
void SwitchVerticesAlgorithm::MakeNecessaryReplacements(VertexDirectory *dir, Graph *graph)
{
	set<VertexKey>::iterator it;
	set<VertexKey> verticesReplaced;

	for (it = m_InterchangeableVertices.begin(); it != m_InterchangeableVertices.end(); it++)
	{
		Vertex *currentVertex;
		if (dir == NULL)
		{
			currentVertex = dir->GetStaticCopyVertex(*it);
		} else
		{
			currentVertex = dir->GetWorkingCopyVertex(*it);
		}

		if (!currentVertex->Interchangeable() || !currentVertex->IsInGraph())
		{
			verticesReplaced.insert(currentVertex->Name());
			continue;
		}

		if (!currentVertex->CanReturnToOriginalGroup())
		{
			Debug::PrintDebugMsg("Had to replace interchangeable");
			currentVertex->Replace(graph);
			// Erase later so we don't ruin the iterator!
			verticesReplaced.insert(currentVertex->Name());
		}
	}

	// Go over list again and erase the vertices we need
	for (it = verticesReplaced.begin(); it != verticesReplaced.end(); it++)
	{
		set<VertexKey>::iterator foundVertex = m_InterchangeableVertices.find(*it);
		if (foundVertex == m_InterchangeableVertices.end())
		{
			throw new GraphColoringException("Vertex is missing from interchangeable list!");
		}
		m_InterchangeableVertices.erase(foundVertex);
	}
}

//------------------------------------------------------------------------------
// MakeNecessaryReplacements: checks the interchangeable list for vertices that
// have to be replaced because they cannot return to their original group
// and replaces them
//---------------------------------------------------------------------------------
void SwitchVerticesAlgorithm::MakeNecessaryReplacementsForVertexSets(Graph *graph)
{
	set<VertexSetKey>::iterator it;
	set<VertexSetKey> verticesReplaced;

	for (it = m_InterchangeableVertexSets.begin(); it != m_InterchangeableVertexSets.end(); it++)
	{
		VertexSet *currentVertex = VertexDirectory::GetVertexSet(*it);		
	
		if (!currentVertex->Interchangeable())
		{
			// Erase later so we don't ruin the iterator!
			verticesReplaced.insert(currentVertex->Name());
			continue;
		}

		if (!currentVertex->CanReturnToOriginalGroup())
		{
			Debug::PrintDebugMsg("Had to replace interchangeable "+currentVertex->PrintName());
			currentVertex->Replace(graph);
			// Erase later so we don't ruin the iterator!
			verticesReplaced.insert(currentVertex->Name());
		}
	}

	// Go over list again and erase the vertices we need
	for (it = verticesReplaced.begin(); it != verticesReplaced.end(); it++)
	{
		set<VertexSetKey>::iterator foundVertex = m_InterchangeableVertexSets.find(*it);
		if (foundVertex == m_InterchangeableVertexSets.end())
		{
			throw new GraphColoringException("Vertex set is missing from interchangeable list!");
		}
		m_InterchangeableVertexSets.erase(foundVertex);
	}
}


//---------------------------------------------------------------------------------
// ClearAllInterchangeableInformation: Removes all interchangeable information from
// vertices
//---------------------------------------------------------------------------------
void SwitchVerticesAlgorithm::ClearAllInterchangeableInformation(VertexDirectory *dir)
{
	map<VertexKey,Vertex*> *allVertices = dir->GetWorkingCopyVertices();
	map<VertexKey,Vertex*>::iterator it;
	for (it= allVertices->begin(); it != allVertices->end(); it++)
	{
		it->second->ClearInterchangeableInformation();
	}
	VertexDirectory::ClearAllVertexSets();
	m_InterchangeableVertexSets.clear();
	m_InterchangeableVertices.clear();
}